import pprint as pp
class Solution:
	# @param {character[][]} board
	# @return {void} Do not return anything, modify board in-place instead.
	def solve(self, board):
		row = len(board)
		if row <= 2:
			return
		col = len(board[0])
		if col <= 2:
			return
		direx = [0, 1, 0, -1]
		direy = [-1, 0, 1, 0]
		seed = set((n, m) for n in [0, row-1] for m in range(0, col) if board[n][m] == 'O')
		seed.update((n, m) for n in range(0, row) for m in [0, col-1] if board[n][m] == 'O')
		while len(seed) > 0:
			tn, tm = seed.pop()
			board[tn][tm] = 'm'
			for i in range(4):
				nn, nm = tn + direy[i], tm + direx[i]
				if nn >=0 and nn < row and nm >=0 and nm < col and board[nn][nm] == 'O':
					seed.add((nn, nm))
		
		for i in range(row):
			for j in range(col):
				if board[i][j] == 'O':
					board[i][j] = 'X'
				elif board[i][j] == 'm':
					board[i][j] = 'O'

if __name__ == '__main__':
	board = [
		list("XXX"),
		list("XOX"),
		list("XXX")
	]
	Solution().solve(board)
	pp.pprint(board)
